/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-12-16
 * Time: 下午 06:57
 */
public class AVLTree {
    static class TreeNode {
        public int val;
        //平衡因子
        public int bf;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;

    /**
     * 插入节点
     *
     * @param val 插入节点的值
     */
    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            root = node;
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = cur.parent;
        while (cur != null) {
            parent = cur;
            if (cur.val == val) return false;
            else if (cur.val < val) cur = cur.right;
            else cur = cur.left;
        }
        if (parent.val < val) parent.right = node;
        else parent.left = node;
        node.parent = parent;
        cur = node;
        //调节平衡因子
        while () {
            if (cur == parent.right) parent.bf++;
            else parent.bf--;
            if (parent.bf == 0) {
                //已经平衡
                break;
            } else if (parent.bf == 1 || parent.bf == -1) {
                cur = parent;
                parent = cur.parent;
            } else {
                if (parent.bf == 2) {
                    if (cur.bf == 1) {

                    } else {
                        //cur.bf == -1
                    }
                } else {
                    //parent.bf == -2
                    if (cur.bf == 1) {

                    } else {
                        //cur.bf == -1
                        //右旋
                        rotateRight(parent);
                    }
                }

            }
        }
    }

    /**
     * 右旋
     * @param parent 需要右旋的节点
     */
    private void rotateRight (TreeNode parent) {
        TreeNode cur = parent.left;
        TreeNode curRight = cur.right;
        TreeNode parentP = parent.parent;
        cur.right = parent;
        cur.parent = parent.parent;
        if (parent == root) root = cur;
        else {
            if (parentP.right == parent) parentP.right = cur;
            else parentP.left = cur;
        }
        parent.parent = cur;
        parent.left = curRight;
        if (curRight != null) curRight.parent = parent;
        cur.bf = 0;
        parent.bf = 0;
    }
}
